package com.example.hot100;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 *  请你找出符合题意的 最短 子数组，并输出它的长度。
 *
 *  示例 1：
 * 输入：nums = [2,6,4,8,10,9,15]
 * 输出：5
 * 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 *
 *  示例 2：
 * 输入：nums = [1,2,3,4]
 * 输出：0
 *
 *  示例 3：
 * 输入：nums = [1]
 * 输出：0
 */
public class Leetcode581_FindUnsortedSubarray {
    public static void main(String[] args) {
        int[] nums = {2, 6, 4, 8, 10, 9, 15};
//        nums = new int[] {1, 2, 5, 4};
        System.out.println(new Solution().findUnsortedSubarray(nums));
    }

    static class Solution {
        /**
         *假设 numsB 在 nums 中对应区间为 [left,right]。
         * 可以发现到 numsB 和 numsC 中任意一个数都大于等于 numsA 中任意一个数
         * 即：numsA中的任意numsA[i] <= nums[j] (0 <= i<= left ;left + 1 <= j <= nums.length - 1)
         * @param nums
         * @return
         */
        public int findUnsortedSubarray2(int[] nums) {
            int maxVal = Integer.MIN_VALUE;  // 记录当前值nums[i]之前的最大值(区间(0 ~ i))
            int minVal = Integer.MAX_VALUE; // 记录当前值nums[i]之后的最小值(区间(i + 1 ~ length - 1))
            int left = -1, right = -1; // 代表 numsB的左右边界
            for (int i = 0; i < nums.length; i++) {
                if (minVal < nums[nums.length - i - 1]) left = nums.length - i - 1;
                else minVal = nums[nums.length - i - 1];

                if (maxVal > nums[i]) right = i;
                else maxVal = nums[i];
            }
            return right == -1 ? 0 : right - left + 1;
        }

        /**
         * 解法一：与排序后的数组进行对比
         * 将给定的数组 nums 表示为三段子数组拼接的形式，分别记作 numsA，numsB，numsC
         * numsA和numsC为排序好的前后缀，numsB为未排序的子数组
         *
         * 将原数组 nums 排序与原数组进行比较，取最长的相同的前缀为 numsA，取最长的相同的后缀为 numsC，这样就可以取到最短的 numsB
         *
         * @param nums
         * @return
         */
        public int findUnsortedSubarray1(int[] nums) {
            int[] copyed = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copyed);
            System.out.println(Arrays.toString(copyed));
            System.out.println(Arrays.toString(nums));

            int left = 0, right = nums.length - 1;
            while (left <= right && (nums[left] == copyed[left] || nums[right] == copyed[right])) {
                if (nums[left] == copyed[left]) ++left;
                if (nums[right] == copyed[right]) --right;
            }
            return left > right ? 0 : right - left + 1;
        }

        public int findUnsortedSubarray(int[] nums) {
            return findUnsortedSubarray2(nums);
        }
    }
}